package leetcode;

import java.util.HashMap;

public class sixteen3 {
    public static boolean isWindowValid(HashMap<Character, Integer> windowMap,
                                        HashMap<Character, Integer> targetMap) {
        for (char key : targetMap.keySet()) {
            if (windowMap.getOrDefault(key, 0) < targetMap.get(key)) {
                return false;
            }
        }
        return true;
    }

    public static String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m < n) {
            return "";
        }

        // 统计t中字符出现次数
        HashMap<Character, Integer> targetMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = t.charAt(i);
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        String minWindow = "";
        int minLength = Integer.MAX_VALUE;
        HashMap<Character, Integer> windowMap = new HashMap<>();

        for (int right = 0; right < m; right++) {
            char rightChar = s.charAt(right);
            // 只统计t中存在的字符
            if (targetMap.containsKey(rightChar)) {
                windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
            }

            // 检查当前窗口是否有效
            while (isWindowValid(windowMap, targetMap)) {
                // 更新最小窗口
                int currentLength = right - left + 1;
                if (currentLength < minLength) {
                    minLength = currentLength;
                    minWindow = s.substring(left, right + 1);
                }

                // 收缩左边界
                char leftChar = s.charAt(left);
                if (targetMap.containsKey(leftChar)) {
                    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                    // 如果计数为0，从窗口中移除
                    if (windowMap.get(leftChar) == 0) {
                        windowMap.remove(leftChar);
                    }
                }
                left++;
            }
        }

        return minWindow;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String result = minWindow(s, t);
        System.out.println(result); // 输出 "BANC"
    }
}
